/*
    Q: 一个楼梯有 10 级台阶，你从下往上走，每跨一步只能向上迈 1 级或者 2 级台阶，请问一共有多少种走法？
    A: 
        状态转移方程：F(X) = F(X-1) + F(X+2)
        最优子结构：F(X-1),F(X-2)
        问题边界：F(1),F(2)
*/

/*
    **递归方法**
    算法缺点：复杂度过高，存在重复计算
*/

function ClimbStair_1(n) {
    if (n == 1 || n == 2)
        return n;
    else {
        return ClimbStair_1(n - 1) + ClimbStair_1(n - 2)
    }
}



/*
    算法思路：使用数组对每次F(X)计算结果进行存储，避免重复计算
    算法缺点：空间复杂度过高，每次计算中只需保存F(X)、F(X-1)、F(X-2)的值即可
*/
function ClimbStair_2(n) {
    let arr = []
    arr[0] = 1;
    arr[1] = 2;
    for (let i = 2; i < n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n - 1]
}





function ClimbStair_3(n) {
    let l1 = 1, l2 = 2;
    var l3;
    if (n == 1 || n == 2)
        return n;
    for (let i = 3; i <= n; i++) {
        l3 = l1 + l2;
        l1 = l2;
        l2 = l3
    }
    return l3;
}

console.log(ClimbStair_1(10))
console.log(ClimbStair_2(2))
console.log(ClimbStair_3(10))
